package com.rgs.se.sort;



public class _1Quick2 {
    /*
        快速排序之双向扫描法
    */
    public static void Quick2(int[] arr,int p,int r){
        if(p<r){
            int q = partition2(arr,p,r);
            Quick2(arr,p,q-1);
            Quick2(arr,q+1,r);
        }
    }
    public static int partition2(int[] arr,int p,int r){
        int pivot = arr[p];
        int left = p+1;
        int right = r;
        while(left <= right){
            while (left <= right && arr[left] <= pivot){
                left++;
            }
            while (left <= right && arr[right] >= pivot){
                right--;
            }
            if(left < right){
                SortUtil.Temp(arr,left,right);
            }
        }
        SortUtil.Temp(arr,p,right);
        return right;
    }
}
